// m

// 给定一个非负整数数组nums，数组中每个元素代表在该位置可以跳跃的最大长度，开始位置为数组的第一个下标处
// 要求：计算出到达最后一个下标处的最少的跳跃次数，假设你总能到达数组的最后一个下标处
 
// 解题思路：动态规划（超时）
// 1. 划分阶段，按照位置进行阶段划分
// 2. 定义状态，定义状态dp[i]表示为，跳到下标i所需要的的最小跳跃次数
// 3. 状态转移方程
//      1. 当前位置i，如果之前的位置j能够跳到位置i需要满足：位置j加上位置j所能跳到最远长度要大于等于i，即j + nums[j] >= i
//      2. 跳到下标i所需要的最小跳跃次数则等于满足上述要求的位置j中最小跳跃次数加1，即dp[i] = min(dp[i], dp[j] + 1)
// 4. 初始条件，跳到下标0所需要的的最小跳跃次数为0， 即dp[0] = 0
// 5. 最终结果，最终结果为dp[size-1]

// 时间复杂度： O(n^2)
// 空间复杂度：O(n)


function jump(nums) {
    let size = nums.length
    let dp = new Array(size).fill(Infinity)
    dp[0] = 0

    for (let i = 1; i < size; i++) {
        for (let j = 0; j < i; j++) {
            if (j + nums[j] >= i) {
                dp[i] = Math.min(dp[i], dp[j] + 1)
            }
        }
    }
    return dp[size - 1]
}


// 思路2： 动态规划 + 贪心
// 因为dp[i]是单调递增的，那么在更新dp[i]时，我们找到最早可以跳到i的点j，从该点更新dp[i],即找到满足j+nums[j] >= i的第一个j，使得dp[i] = dp[j] + 1
// 而查找第一个j的过程可以通过使用一个指针变量j从前向后迭代查找

// 时间复杂度：O(n)， 内层遍历只遍历一次
// 空间复杂度：O(n)
function jump(nums) {
    let size = nums.length
    let dp = new Array(size).fill(Infinity)
    dp[0] = 0
    let j = 0
    for (let i = 1; i < size; i++) {
        while (j + nums[j] < i) {
            j += 1
        }
        dp[i] = dp[j] + 1
    }
    return dp[size - 1]
}

// 思路3， 贪心算法
// 在每次可跳范围内选择可以使下一次跳的更远的位置，这样才能获得最少跳跃次数
// 1. 维护几个变量：当前所能达到的最远位置end，下一步能跳到的最远位置max_pos，最少跳跃次数steps
// 2. 遍历数组nums的前len(nums)-1个元素
// 3. 每次更新第i位置下一步所能跳到的最远位置max_pos
// 4. 如果索引i到达了end边界，则：更新end为新的当前位置max_pos,并令步数加1
// 5. 最终返回跳跃次数steps
function jump(nums) {
    let end = 0
    let max_pos = 0
    let steps = 0
    for (let i = 0; i < nums.length - 1; i++) {
        max_pos = Math.max(max_pos, nums[i] + i)
        if (i === end) {
            end = max_pos
            steps += 1
        }
    }
    return steps
}

let nums = [2, 3, 1, 1, 4, 2]
console.log(jump(nums));